package com.yangli.leecode.mashib;

import java.util.Arrays;

/**
 * @Description 贪心算法-金条切割问题
 * @Author liyang
 * @Date 2022/12/30 16:35
 */
public class GoldCut {
    public static void main(String[] args){

        System.out.println(GoldCut.lessMoney1(new int[]{10, 30, 20, 40}));
        System.out.println(GoldCut.lessMoney2(new int[]{10, 30, 20, 40}));

    }

    //暴力解法
    public static int lessMoney1(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //全排列查询，从0位置开始，当前切割话费为0
        return process(arr, 0, 0);
    }

    public static int process(int[] arr, int i, int consume){
        //数组长度为1表示，不需要切割，返回切割消费
        if (arr.length == 1) {
            return consume;
        }
        //当前切割消费
        int sum = Arrays.stream(arr).sum();
        int min = Integer.MAX_VALUE;
        while (i < arr.length) {
            //从0位置开始遍历数组，去递归尝试去掉某个位置的数组，选取子数组消费最小的哪一个
            int[] newArr = cloneAndExclude(arr, i++);
            min = Math.min(min, process(newArr, 0, consume + sum));
        }
        return min;
    }

    public static int[] cloneAndExclude(int[] arr, int i){
        int[] res = new int[arr.length - 1];
        int temp = 0;
        for (int j = 0; j < arr.length; j++) {
            if (j != i) {
                res[temp++] = arr[j];
            }
        }
        return res;
    }

    public static int lessMoney2(int[] arr){
        Arrays.sort(arr);
        if (arr.length == 1) {
            return Arrays.stream(arr).sum();
        }
        int sum = Arrays.stream(arr).sum();
        int res = 0;
        for (int i = arr.length - 1; i > 0; i--) {
            res += sum;
            sum -= arr[i];
        }
        return res;

    }
}
